#include <bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

using namespace std;

#define nullptr NULL // for some oj not supporting c++11.

int getint(int x=0)
{
    char c=getchar(); bool mi = false;
    while(c!='-' && (c<'0' || '9'<c)) c=getchar();
    if(c=='-') { mi=true; c=getchar(); }
    x=c-'0';
    while('0'<=(c=getchar()) && c<='9') x=x*10+c-'0';
    return mi ? -x : x;
}
db getdb(db x=0.0) { scanf("%lf",&x); return x; }


/////////////////////////////////////////////////////
/////////////////////////////////////////////////////

const int INF = (1<<30)-1;

struct edge{ int in; int v; edge*nxt; } pool[505000];
edge*eds[105000]; edge*et=pool;
void addedge(int a,int b,int v){ et->in=b; et->v=v; et->nxt=eds[a]; eds[a]=et++; }
#define FOREACH_EDGE(e,x) for(edge*e=eds[x];e;e=e->nxt)
void GraphInit(int n){ for(int i=0;i<=n;i++) eds[i]=nullptr; et=pool; } 

const int mxn = 105000;

int n,m;
int dist[mxn];
///==================SPFA==================
struct pl
{
    int x; int d;
    bool operator<(const pl& f) const
    { return d > f.d; }
};
priority_queue<pl> q;
inline void relax(int x, int newdist)
{
    if(dist[x] <= newdist) return;
    dist[x] = newdist;
    q.push((pl){x,dist[x]});
}
int SPFA(int source, int sink = 0)
{
    for(int i=1;i<=n;i++) dist[i]=INF;
    q.push((pl){source,0});
    while(!q.empty())
    {
        int x = q.top().x;
        int d = q.top().d;
        q.pop();
        if(d > dist[x]) continue;
        FOREACH_EDGE(e,x) relax(e->in, d + e->v);
    }
    return dist[sink];
}

int main()
{
    while(scanf("%d%d",&n,&m)>0)
    {
        if(n==0 && m==0) break;
        GraphInit(n);
        for(int i=1;i<=m;i++)
        {
            int a=getint(); int b=getint(); int v=getint();
            addedge(a,b,v);
            addedge(b,a,v);
        }
        
        printf("%d\n",Dijkstra(1,n));
    }
    
    return 0;
}
